from typing import List


class Solution:

    """
    方法： trap

    逻辑: 使用动态规划，提前存储当前位置左边和右边的最大高度存入数组，计算当前位置可以存储的雨水量。

    Args:
        height (List[int]): 一个整数数组，表示每个位置的高度。

    Returns:
        int: 可以存储的雨水总量。

    Time: O(n), n为height数组的长度。

    Space: O(n), 需要额外的空间来存储左边和右边的最大高度数组。
    """
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        n = len(height)
        leftMax = [height[0]] + [0] * (n - 1)
        for i in range(1, n):
            leftMax[i] = max(leftMax[i - 1], height[i])

        rightMax = [0] * (n - 1) + [height[n - 1]]
        for i in range( n - 2, -1, -1):
            rightMax[i] = max(rightMax[i + 1], height[i])
       
        ans = sum(min(leftMax[i], rightMax[i]) - height[i] for i in range(n))
        return ans
    
    """
    方法： trap1

    逻辑: 使用双指针法从两端向中间移动，记录当前位置左边和右边的最大高度，计算当前位置可以存储的雨水量。

    Args:
        height (List[int]): 一个整数数组，表示每个位置的高度。

    Returns:
        int: 可以存储的雨水总量。

    Time: O(n), n为height数组的长度。

    Space: O(1), 只使用了常量空间。
    """
    def trap1(self, height: List[int]) -> int:
        left, right = 0, len(height) - 1
        leftMax, rightMax = 0, 0
        ans = 0
        while left < right:
            leftMax = max(leftMax, height[left])
            rightMax = max(rightMax, height[right])
            if leftMax < rightMax:
                ans += leftMax - height[left]
                left += 1
            else:
                ans += rightMax - height[right]
                right -= 1
        return ans


    """
    方法： trap2

    逻辑: 使用栈来存储高度数组的索引，栈顶元素为当前处理的元素。从左到右遍历高度数组，如果当前元素的高度大于栈顶元素，则弹出栈顶元素，计算可以存储的雨水量，并将当前元素的索引压入栈中。

    Args:
        height (List[int]): 一个整数数组，表示每个位置的高度。

    Returns:
        int: 可以存储的雨水总量。

    Time: O(n), n为height数组的长度。

    Space: O(n), 栈的最大深度为n。
    """
    def trap2(self, height: List[int]) -> int:
        ans = 0
        st = []
        for i, h in enumerate(height):
            while st and h >= height[st[-1]]:
                top = st.pop()
                if not st: break
                left = st[-1]
                dh = min(height[left], h) - height[top] #面积的高
                ans += dh * (i - left - 1)
            st.append(i)
        return ans
        